package com.agan.aganalgorithm.trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author agan
 * @ClassName Demo
 * @Description
 * @Date 2021/4/12 2:27 下午
 **/
public class Demo {
    /**
     * 给定的二叉树是{3,9,20,#,#,15,7},
     */

    public static class TreeNode{

        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(){}

        public TreeNode(int val){
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }


    public static void main(String[] args){
        TreeNode treeNode = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        ArrayList<ArrayList<Integer>> arrayLists = levelOrder(treeNode);
        arrayLists.forEach(arrays ->{
            System.out.println(arrays);
        });

    }



    public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode treeNode){
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(treeNode);
        while (!queue.isEmpty()){
            //一层一层获取
            ArrayList<Integer> level = new ArrayList<Integer>();
            int levelNum = queue.size();
            for (int i =0;i<levelNum ; i++){
                if(queue.peek().left != null){
                    queue.offer(queue.peek().left);
                }
                if(queue.peek().right != null){
                    queue.offer(queue.peek().right);
                }
                level.add(queue.poll().val);

            }
            result.add(level);
        }
        return result;
    }
}
